\section{Equivalence}

\begin{theorem}[Equivalence PSpace-C]
Equivalence of SSTs is PSpace-C.
\end{theorem}
\Proof
Don't have one.
\qed



\begin{theorem}[Unary Output Equivalence is PTime]
Equivalence of SSTs over a unary alphabet is in P.
\end{theorem}
\Proof
Yifei's algorithm (please formalize it) and prove correctness.
\qed


\begin{theorem}[Unary Output Equivalence is P-C]
Equivalence of SSTs over a unary alphabet is in PTime-C.
\end{theorem}
\Proof
Don't have one.
Possible problems to try reduction from can be found \href{http://www.cs.armstrong.edu/greenlaw/research/PARALLEL/plist.pdf}{\emph{here}}.
\qed


\begin{theorem}[Unary Output Equivalence for STT]
Given tow STT $\stt_1,\stt_1$ with unary output alphabet checking their equivalence is decidable in ?-TIME.
\end{theorem}
\Proof
Don't have one.
\qed